<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Partial data structures
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial017.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial012.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial019.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc38">3.6</A>&nbsp;&nbsp;Partial data structures</H2>
<A NAME="tail"></A>
<A NAME="@default70"></A>
Logical variables can occur anywhere, not only as arguments of clause
heads and goals, but also within data structures.
A data structure which contains variables is called a partial data
structure, because it will eventually be completed by substituting
the variable with an actual data term.
The most common case of a partial data structure is a list whose
tail is not yet instantiated.<BR>
<BR>
Consider first an example where no partial lists occur.
In the following query, a list is built incrementally,
starting from its end:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- L1 = [], L2 = [c|L1], L3 = [b|L2], L4 = [a|L3].
L1 = []
L2 = [c]
L3 = [b, c]
L4 = [a, b, c]
</PRE></BLOCKQUOTE>
Whenever a new head/tail cell is created,
the tail is already instantiated to a complete list.<BR>
<BR>
But it is also possible to build the list from the front.
The following code, in which the goals have been reordered,
gives the same final result as the code above:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- L4 = [a|L3], L3 = [b|L2], L2 = [c|L1], L1 = [].
L1 = []
L2 = [c]
L3 = [b, c]
L4 = [a, b, c]
</PRE></BLOCKQUOTE>
However, in the course of the computation, variables get instantiated to
&#8221;partial lists&#8221;, i.e. lists whose head is known, but whose tail is not.
This is perfectly legal: due to the nature of the logical variable, the
tail can be filled in later by instantiating the variable.<BR>
<BR>
<HR>
<A HREF="tutorial017.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial012.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial019.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
